package demo4;
import java.util.*;
public class Solution {
    //1.面试题 01.04. 回文排列(哈希计数法)
    public boolean canPermutePalindrome(String s) {
        //哈希计数法：保证一个字母是奇数个，其他字母是偶数个
        HashMap<Character, Integer> hash = new HashMap<>();
        //计数
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if(!hash.containsKey(ch)){
                hash.put(ch, 1);
            }else{
                hash.put(ch, hash.get(ch) + 1);
            }
        }
        int count = 0;//统计出现奇数的个数
        for(char ch : hash.keySet()){
            int k = hash.get(ch);
            if(k % 2 != 0){
                count++;
            }
        }
        return count > 1 ? false : true;
    }
    //2.面试题 01.05. 一次编辑(硬解，但效果不错)
    public boolean oneEditAway(String first, String second) {
        //先排除增加或删除的
        int fLen = first.length();
        int sLen = second.length();
        if(fLen < sLen){//让大的是first
            return oneEditAway(second, first);
        }
        if(fLen - sLen > 1){
            return false;
        }
        //接下来是排除替换的，也有可能是增删只有一个的
        //排除替换的
        if(fLen == sLen){
            int count = 0;
            for(int i = 0; i < fLen; i++){
                if(first.charAt(i) != second.charAt(i)){
                    count++;
                }
            }
            if(count > 1){
                return false;
            }
        }
        //这时，只有多出一个但其余相等的是正确的
        if(fLen - sLen == 1){
            int count = 0;
            int index = 0;//second下标
            for(int i = 0; i < fLen; i++){
                if(index < sLen && first.charAt(i) != second.charAt(index)){
                    count++;
                }else{
                    index++;
                }
            }
            if(count > 1){
                return false;
            }
        }
        return true;
    }
    //3.面试题 01.07. 旋转矩阵(模拟)
    public void rotate(int[][] matrix) {
        //先对角线反转，再镜面反转
        int row = matrix[0].length;//行
        int col = matrix.length;//列
        //对角线反转
        for(int i = 0; i < row; i++){
            for(int j = 0; j < i; j++){
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = tmp;
            }
        }
        //左右反转
        for(int i = 0; i < row; i++){
            int left = 0;
            int right = col - 1;
            while(left < right){
                int tmp = matrix[i][left];
                matrix[i][left] = matrix[i][right];
                matrix[i][right] = tmp;
                left++;
                right--;
            }
        }
    }
    //4.面试题 01.09. 字符串轮转(绝杀)
    public boolean isFlipedString(String s1, String s2) {
        //保证s1与s2相等的前提下，将两个s1拼接起来，然后看s2是否为其字串
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
    //5.面试题 10.05. 稀疏数组搜索(二分升级版)
    public int findString(String[] words, String s) {
        //二分查找
        int left = 0;
        int right = words.length - 1;
        while(left <= right){
            while(words[left].equals("")){
                left++;
            }
            while(words[right].equals("")){
                right--;
            }
            int mid = (left + right) / 2;
            //遇到空格mid左右走都可以
            while(left < mid && words[mid].equals("")){
                mid--;
            }
            if(s.compareTo(words[mid]) < 0){
                right = mid - 1;
            }else if(s.compareTo(words[mid]) > 0){
                left = mid + 1;
            }else{
                return mid;
            }
        }
        return -1;
    }
    //6.面试题 01.08. 零矩阵(标记位法)
    public void setZeroes(int[][] matrix) {
        int r = matrix.length;
        int c = matrix[0].length;
        //额外建立一个标记数组,这个标记数组每个元素用来表示行和列
        //若某个数为零，就把这一行和这一列标记为0
        boolean[] row = new boolean[r];
        boolean[] col = new boolean[c];
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(matrix[i][j] == 0){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        //最后遍历原数组，若这行/列存在标记位，就放0
        for(int i = 0; i < r; i++){
            for(int j = 0; j < c; j++){
                if(row[i] || col[j]){
                    matrix[i][j] = 0;
                }
            }
        }
    }
    //8.面试题 10.02. 变位词组(哈希表(难))
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for(int i = 0; i < strs.length; i++){
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String str = String.valueOf(arr);
            if(!hash.containsKey(str)){
                List<String> list = new ArrayList<>();
                list.add(strs[i]);
                hash.put(str, list);
            }else{
                hash.get(str).add(strs[i]);
            }
        }
        return new ArrayList<>(hash.values());
    }

    //8。反转字符串 II(模拟)
    public String reverseStr(String s, int k) {
        char[] arr = s.toCharArray();
        int len = s.length();
        //题意：每隔K个反转K个
        for(int i = 0; i < len; i += 2*k){
            reverse(arr, i, Math.min(i + k, len) - 1);
        }
        return String.valueOf(arr);
    }
    //反转字符串
    private void reverse(char[] arr, int left, int right){
        while(left < right){
            char tmp = arr[left];
            arr[left] = arr[right];
            arr[right] = tmp;
            left++;
            right--;
        }
    }
    //9.检测大写字母(模拟)
    public boolean detectCapitalUse(String word) {
        int len = word.length();
        int count = 0;//记录大写字母的数量
        boolean flag = false;
        for(int i = 0; i < len; i++){
            char ch = word.charAt(i);
            if(ch >= 'A' && ch <= 'Z'){
                count++;
                if(i == 0){
                    flag = true;
                }
            }
        }
        if(count == len){
            return true;
        }else if(count == 1 && len > 1 && flag){
            return true;
        }else if(count == 0){
            return true;
        }else{
            return false;
        }
    }
    //10.Excel 表列序号(模拟10进制)
    public int titleToNumber(String columnTitle) {
        //从后向前，按权位为26分
        int sum = 0;
        int len = columnTitle.length();
        for(int i = len - 1; i >= 0; i--){
            char ch = columnTitle.charAt(i);
            sum += (ch - 'A' + 1) * Math.pow(26, len - i - 1);
        }
        return sum;
    }
}
//7.面试题 16.02. 单词频率(哈希法)
class WordsFrequency {
    public Map<String, Integer> map = new HashMap<>();
    public WordsFrequency(String[] book) {
        for(int i = 0; i < book.length; i++){
            if(!map.containsKey(book[i])){
                map.put(book[i], 1);
            }else{
                map.put(book[i], map.get(book[i]) + 1);
            }
        }
    }

    public int get(String word) {
        if(!map.containsKey(word)){
            return 0;
        }else{
            return map.get(word);
        }
    }
}
